\contentsline {chapter}{\tocchapter {Chapter}{1}{Introduction: the origin of words}}{7}{chapter.1}
\contentsline {chapter}{\tocchapter {Chapter}{2}{Main Definitions}}{9}{chapter.2}
\contentsline {section}{\tocsection {}{2.1}{Words}}{9}{section.2.1}
\contentsline {subsection}{\tocsubsection {}{2.1.1}{The free semigroup}}{9}{subsection.2.1.1}
\contentsline {subsection}{\tocsubsection {}{2.1.2}{Orders on words}}{10}{subsection.2.1.2}
\contentsline {subsection}{\tocsubsection {}{2.1.3}{Commuting words}}{10}{subsection.2.1.3}
\contentsline {section}{\tocsection {}{2.2}{Graphs}}{12}{section.2.2}
\contentsline {subsection}{\tocsubsection {}{2.2.1}{Basic definitions}}{12}{subsection.2.2.1}
\contentsline {subsection}{\tocsubsection {}{2.2.2}{Automata}}{12}{subsection.2.2.2}
\contentsline {subsection}{\tocsubsection {}{2.2.3}{Graphs in the sense of Serre}}{13}{subsection.2.2.3}
\contentsline {subsection}{\tocsubsection {}{2.2.4}{Inverse automata and foldings}}{13}{subsection.2.2.4}
\contentsline {subsection}{\tocsubsection {}{2.2.5}{Mealy automata}}{13}{subsection.2.2.5}
\contentsline {section}{\tocsection {}{2.3}{Universal Algebra}}{13}{section.2.3}
\contentsline {subsection}{\tocsubsection {}{2.3.1}{Basic definitions}}{13}{subsection.2.3.1}
\contentsline {subsection}{\tocsubsection {}{2.3.2}{Free algebras in varieties}}{15}{subsection.2.3.2}
\contentsline {subsection}{\tocsubsection {}{2.3.3}{The Birkhoff theorem}}{16}{subsection.2.3.3}
\contentsline {subsection}{\tocsubsection {}{2.3.4}{Locally finite varieties}}{16}{subsection.2.3.4}
\contentsline {subsection}{\tocsubsection {}{2.3.5}{The Burnside problem for varieties of algebras}}{18}{subsection.2.3.5}
\contentsline {subsection}{\tocsubsection {}{2.3.6}{Finitely based and Cross varieties}}{18}{subsection.2.3.6}
\contentsline {subsection}{\tocsubsection {}{2.3.7}{Inherently non-finitely based finite algebras: the link between finite and infinite}}{19}{subsection.2.3.7}
\contentsline {section}{\tocsection {}{2.4}{Growth of algebras}}{23}{section.2.4}
\contentsline {section}{\tocsection {}{2.5}{Symbolic Dynamics}}{24}{section.2.5}
\contentsline {subsection}{\tocsubsection {}{2.5.1}{Basic definitions}}{24}{subsection.2.5.1}
\contentsline {subsection}{\tocsubsection {}{2.5.2}{Subshifts}}{25}{subsection.2.5.2}
\contentsline {section}{\tocsection {}{2.6}{Rewriting systems}}{27}{section.2.6}
\contentsline {subsection}{\tocsubsection {}{2.6.1}{The main definitions}}{27}{subsection.2.6.1}
\contentsline {subsection}{\tocsubsection {}{2.6.2}{Confluence}}{27}{subsection.2.6.2}
\contentsline {subsection}{\tocsubsection {}{2.6.3}{What if a rewriting system is not confluent? The art of Knuth-Bendix}}{30}{subsection.2.6.3}
\contentsline {subsection}{\tocsubsection {}{2.6.4}{String rewriting}}{31}{subsection.2.6.4}
\contentsline {section}{\tocsection {}{2.7}{Presentations of semigroups}}{33}{section.2.7}
\contentsline {subsection}{\tocsubsection {}{2.7.1}{Semigroups and monoids: basic definitions}}{33}{subsection.2.7.1}
\contentsline {subsection}{\tocsubsection {}{2.7.2}{Congruences, ideals and quotient semigroups}}{35}{subsection.2.7.2}
\contentsline {subsection}{\tocsubsection {}{2.7.3}{String rewriting and presentations}}{35}{subsection.2.7.3}
\contentsline {subsection}{\tocsubsection {}{2.7.4}{The free group}}{37}{subsection.2.7.4}
\contentsline {subsection}{\tocsubsection {}{2.7.5}{The growth function, growth series and Church-Rosser presentations}}{37}{subsection.2.7.5}
\contentsline {subsection}{\tocsubsection {}{2.7.6}{The Cayley graphs}}{39}{subsection.2.7.6}
\contentsline {chapter}{\tocchapter {Chapter}{3}{Synchronizing Automata and Road Coloring}}{41}{chapter.3}
\contentsline {section}{\tocsection {}{3.1}{Complete Automata}}{41}{section.3.1}
\contentsline {section}{\tocsection {}{3.2}{Synchronizing Automata}}{41}{section.3.2}
\contentsline {section}{\tocsection {}{3.3}{The \v {C}ern\'{y} conjecture}}{43}{section.3.3}
\contentsline {section}{\tocsection {}{3.4}{The Road Coloring Problem}}{45}{section.3.4}
\contentsline {section}{\tocsection {}{3.5}{Applications of the Road Coloring Theorem}}{54}{section.3.5}
\contentsline {subsection}{\tocsubsection {}{3.5.1}{Application to symbolic dynamics}}{54}{subsection.3.5.1}
\contentsline {subsection}{\tocsubsection {}{3.5.2}{Application to coding theory}}{56}{subsection.3.5.2}
\contentsline {chapter}{\tocchapter {Chapter}{4}{Avoidable Words}}{61}{chapter.4}
\contentsline {section}{\tocsection {}{4.1}{An Old Example}}{61}{section.4.1}
\contentsline {section}{\tocsection {}{4.2}{Proof of Thue's Theorem}}{62}{section.4.2}
\contentsline {section}{\tocsection {}{4.3}{Square-Free Words}}{63}{section.4.3}
\contentsline {section}{\tocsection {}{4.4}{$k$th power-free substitutions}}{64}{section.4.4}
\contentsline {section}{\tocsection {}{4.5}{Avoidable words}}{65}{section.4.5}
\contentsline {subsection}{\tocsubsection {}{4.5.1}{Examples and Simple Facts}}{65}{subsection.4.5.1}
\contentsline {subsection}{\tocsubsection {}{4.5.2}{The Zimin Theorem}}{66}{subsection.4.5.2}
\contentsline {subsection}{\tocsubsection {}{4.5.3}{Fusions, Free Subsets and Free Deletions}}{66}{subsection.4.5.3}
\contentsline {subsection}{\tocsubsection {}{4.5.4}{The Bean-Ehrenfeucht-McNulty+Zimin Theorem}}{67}{subsection.4.5.4}
\contentsline {subsection}{\tocsubsection {}{4.5.5}{The Proof of $(3)\rightarrow (2)$}}{67}{subsection.4.5.5}
\contentsline {subsection}{\tocsubsection {}{4.5.6}{The Proof of $(2)\rightarrow (1)$}}{67}{subsection.4.5.6}
\contentsline {subsection}{\tocsubsection {}{4.5.7}{Proof of $(1)\rightarrow (3)$}}{67}{subsection.4.5.7}
\contentsline {subsection}{\tocsubsection {}{4.5.8}{Simultaneous avoidability}}{69}{subsection.4.5.8}
\contentsline {chapter}{\tocchapter {Chapter}{5}{Semigroups}}{71}{chapter.5}
\contentsline {section}{\tocsection {}{5.1}{Structure of semigroups}}{71}{section.5.1}
\contentsline {subsection}{\tocsubsection {}{5.1.1}{Periodic semigroups}}{72}{subsection.5.1.1}
\contentsline {subsection}{\tocsubsection {}{5.1.2}{Periodic semigroups with exactly one idempotent}}{72}{subsection.5.1.2}
\contentsline {subsection}{\tocsubsection {}{5.1.3}{Finite nil-semigroups.}}{73}{subsection.5.1.3}
\contentsline {section}{\tocsection {}{5.2}{Free Semigroups and Varieties}}{74}{section.5.2}
\contentsline {subsection}{\tocsubsection {}{5.2.1}{Free Rees Factor-Semigroups}}{74}{subsection.5.2.1}
\contentsline {subsection}{\tocsubsection {}{5.2.2}{A Description of Free Semigroups}}{74}{subsection.5.2.2}
\contentsline {section}{\tocsection {}{5.3}{The Burnside Problem for Varieties}}{76}{section.5.3}
\contentsline {subsection}{\tocsubsection {}{5.3.1}{Symbolic Dynamics and Semigroups}}{78}{subsection.5.3.1}
\contentsline {subsection}{\tocsubsection {}{5.3.2}{An application of dynamical systems to semigroups}}{79}{subsection.5.3.2}
\contentsline {subsection}{\tocsubsection {}{5.3.3}{Implication $2\rightarrow 4$}}{82}{subsection.5.3.3}
\contentsline {section}{\tocsection {}{5.4}{Brown's theorem and uniformly recurrent words}}{86}{section.5.4}
\contentsline {section}{\tocsection {}{5.5}{Burnside Problems and the Finite Basis Property}}{87}{section.5.5}
\contentsline {section}{\tocsection {}{5.6}{Inherently Non-Finitely Based Finite Semigroups}}{88}{section.5.6}
\contentsline {subsection}{\tocsubsection {}{5.6.1}{Some advanced semigroup theory}}{88}{subsection.5.6.1}
\contentsline {subsubsection}{\tocsubsubsection {}{5.6.1.1}{Ideals and $0$-simple semigroups}}{88}{subsubsection.5.6.1.1}
\contentsline {subsubsection}{\tocsubsubsection {}{5.6.1.2}{Semigroups without divisors isomorphic to $A_2$ and $B_2$}}{91}{subsubsection.5.6.1.2}
\contentsline {subsection}{\tocsubsection {}{5.6.2}{The description of inherently nonfinitely based\ finite semigroups}}{93}{subsection.5.6.2}
\contentsline {section}{\tocsection {}{5.7}{Growth functions of semigroups}}{101}{section.5.7}
\contentsline {subsection}{\tocsubsection {}{5.7.1}{The definition}}{101}{subsection.5.7.1}
\contentsline {subsection}{\tocsubsection {}{5.7.2}{Chebyshev, Hardy-Ramanujan and a semigroup of intermediate growth}}{102}{subsection.5.7.2}
\contentsline {subsection}{\tocsubsection {}{5.7.3}{Growth of relatively free semigroups in varieties}}{103}{subsection.5.7.3}
\contentsline {section}{\tocsection {}{5.8}{Inverse semigroups}}{104}{section.5.8}
\contentsline {subsection}{\tocsubsection {}{5.8.1}{Basic facts about inverse semigroups}}{104}{subsection.5.8.1}
\contentsline {subsection}{\tocsubsection {}{5.8.2}{Free inverse semigroups, E-unitary covers and semigroups of automata}}{104}{subsection.5.8.2}
\contentsline {subsection}{\tocsubsection {}{5.8.3}{Identities of finite inverse semigroups, Zimin words, and symbolic dynamics}}{104}{subsection.5.8.3}
\contentsline {chapter}{\tocchapter {Chapter}{6}{Rings}}{109}{chapter.6}
\contentsline {section}{\tocsection {}{6.1}{The basic notions}}{109}{section.6.1}
\contentsline {section}{\tocsection {}{6.2}{Free Associative Algebras}}{109}{section.6.2}
\contentsline {section}{\tocsection {}{6.3}{Burnside-type Problems in Associative Algebras}}{109}{section.6.3}
\contentsline {subsection}{\tocsubsection {}{6.3.1}{Introduction}}{109}{subsection.6.3.1}
\contentsline {subsection}{\tocsubsection {}{6.3.2}{Shirshov's Height Theorem}}{111}{subsection.6.3.2}
\contentsline {subsection}{\tocsubsection {}{6.3.3}{The Dubnov-Ivanov-Nagata-Higman Theorem}}{114}{subsection.6.3.3}
\contentsline {subsection}{\tocsubsection {}{6.3.4}{Golod Counterexamples to the Kurosh Problem}}{116}{subsection.6.3.4}
\contentsline {subsection}{\tocsubsection {}{6.3.5}{Zimin words and the Baer radical}}{120}{subsection.6.3.5}
\contentsline {subsection}{\tocsubsection {}{6.3.6}{The restricted Burnside problem for associative rings and inherently nonfinitely based\ varieties of rings}}{122}{subsection.6.3.6}
\contentsline {section}{\tocsection {}{6.4}{The finite basis problem}}{122}{section.6.4}
\contentsline {subsection}{\tocsubsection {}{6.4.1}{Basic facts about finite associative rings}}{122}{subsection.6.4.1}
\contentsline {subsection}{\tocsubsection {}{6.4.2}{Negative result}}{124}{subsection.6.4.2}
\contentsline {subsection}{\tocsubsection {}{6.4.3}{Positive result. Identities of finite rings}}{127}{subsection.6.4.3}
\contentsline {chapter}{\tocchapter {Chapter}{7}{Groups}}{131}{chapter.7}
\contentsline {section}{\tocsection {}{7.1}{Basic facts and constructions}}{131}{section.7.1}
\contentsline {subsection}{\tocsubsection {}{7.1.1}{Constructions}}{131}{subsection.7.1.1}
\contentsline {subsection}{\tocsubsection {}{7.1.2}{Commutators}}{131}{subsection.7.1.2}
\contentsline {subsection}{\tocsubsection {}{7.1.3}{Group presentations}}{132}{subsection.7.1.3}
\contentsline {subsection}{\tocsubsection {}{7.1.4}{Van Kampen diagrams:the definition}}{132}{subsection.7.1.4}
\contentsline {subsection}{\tocsubsection {}{7.1.5}{Van Kampen diagrams and tilings. An elementary school problem and its non-elementary solution}}{134}{subsection.7.1.5}
\contentsline {subsection}{\tocsubsection {}{7.1.6}{Fundamental groups and 2-complexes}}{135}{subsection.7.1.6}
\contentsline {subsection}{\tocsubsection {}{7.1.7}{The Squier complex of a string rewriting system}}{136}{subsection.7.1.7}
\contentsline {section}{\tocsection {}{7.2}{The Burnside problem for groups}}{136}{section.7.2}
\contentsline {subsection}{\tocsubsection {}{7.2.1}{Positive results}}{136}{subsection.7.2.1}
\contentsline {subsection}{\tocsubsection {}{7.2.2}{Golod's Counterexample to the Unbounded Burnside Problem For Groups}}{137}{subsection.7.2.2}
\contentsline {subsection}{\tocsubsection {}{7.2.3}{The bounded Burnside problem}}{138}{subsection.7.2.3}
\contentsline {subsection}{\tocsubsection {}{7.2.4}{The restricted Burnside problem, Zimin words, and inherently nonfinitely based\ varieties of groups}}{138}{subsection.7.2.4}
\contentsline {section}{\tocsection {}{7.3}{The finite basis problem for group varieties}}{138}{section.7.3}
\contentsline {subsection}{\tocsubsection {}{7.3.1}{An example of Yu. Kleiman}}{138}{subsection.7.3.1}
\contentsline {subsection}{\tocsubsection {}{7.3.2}{Construction of the algebra $R$ used in Subsection\nonbreakingspace \ref {rings without finite identity basis}}}{140}{subsection.7.3.2}
\contentsline {subsection}{\tocsubsection {}{7.3.3}{Metabelian groups}}{144}{subsection.7.3.3}
\contentsline {section}{\tocsection {}{7.4}{Groups and identities, Ab\'ert's criterium}}{145}{section.7.4}
\contentsline {section}{\tocsection {}{7.5}{Groups and rewriting systems}}{146}{section.7.5}
\contentsline {subsection}{\tocsubsection {}{7.5.1}{Diagrams as 2-dimensional words, diagram groups}}{146}{subsection.7.5.1}
\contentsline {subsection}{\tocsubsection {}{7.5.2}{The R.Thompson group $F$}}{147}{subsection.7.5.2}
\contentsline {subsection}{\tocsubsection {}{7.5.3}{Further properties of the Thompson group}}{150}{subsection.7.5.3}
\contentsline {chapter}{\tocchapter {Chapter}{}{Bibliography}}{153}{theorem.7.5.23}
\contentsline {chapter}{\tocchapter {Chapter}{}{Index}}{159}{chapter*.1}
